package medium

/*
时间复杂度:O(n+∣Σ∣) ∣Σ∣表示字
空间复杂度:O(∣Σ∣)

难点:如何将最多的字符x与其他字符y摆成符合要求(相邻两个字符不相同)状态

1.首先,字符最多不超过n/2+1,即x-y<=1(x最多也只比y多1)
2.一个索引从0开始的列表,偶数索引个数一定>=奇数索引个数(0 1 2  偶数索引为0 2, 奇数索引1)
3.所以一开始应该将出现次数最多的字符放入偶数索引idx,等放完后,再遍历整个cnt(统计每个字符出现的次数),将还没放的放到idx
4.如果idx>=n, 表示偶数索引用完了,接下来放奇数索引,令idx从1开始
*/

func reorganizeString(s string) string {
	cnt := [26]int{}
	maxVal := 0
	var ch byte
	for i := range s {
		t := s[i] - 'a'
		cnt[t]++
		if maxVal < cnt[t] {
			maxVal = cnt[t]
			ch = s[i]
		}
	}
	// 要满足条件,设出现最多次的字符数量为x,其他字符数量总和为y, x<=y+1 => 2x<=x+y+1 => 2x<=n+1 => x<=n/2+1
	// 若x>n/2+1, 则无法构成符合条件的字符串
	if maxVal > (len(s)+1)/2 {
		return ""
	}

	// 创建结果列表,将字母间隔放到对应的位置上
	result := make([]byte, len(s))
	// 由于ch为出现最多次的字符串,则将其放到索引为偶数的位置上(索引从0开始,无论长度为多少,所以为偶数的数量和肯定>=索引为奇数的数量和)
	idx := 0
	for cnt[ch-'a'] > 0 {
		result[idx] = ch
		cnt[ch-'a']--
		idx += 2
	}
	for i := range cnt {
		for cnt[i] > 0 {
			if idx >= len(s) {
				idx = 1
			}
			cnt[i]--
			result[idx] = byte(i + 'a')
			idx += 2
		}
	}
	return string(result)
}